#!/usr/bin/env python
# -*- coding: utf8 -*-
#-------------------------------------------------------------------------------
# Name:        tree.py
# Purpose:     树的创建和遍历
#
# Author:      iori
#
# Created:     02/11/2014
# Copyright:   (c) iori 2014
# Licence:     GPLv3
#-------------------------------------------------------------------------------
from __future__ import print_function
from functools import partial

import unittest

class Node(object):
    def __init__(self, v, lc=None, rc=None):
        self.v = v
        self.lc = lc
        self.rc = rc

class Tree(object):
    def __init__(self, s):
        ''' constuct a tree from string, where # express null node
        '''
        self.s = s
        self.root = self.create(iter(s))

    def create(self, it):
        ''' here we a iterable as arguments, it is consumed. '''
        v = next(it, None)
        if not v:
            raise ValueError('Unable to build a tree from string: {}'.format(self.s))
        if v == '#':
            return None
        else:
            return Node(v, self.create(it), self.create(it))

    def preorder(self, visit):
        ''' recrusive pre order traverse a tree '''
        def pre(node):
            if node:
                visit(node)
            if node.lc:
                pre(node.lc)
            if node.rc:
                pre(node.rc)

        pre(self.root)

    def postorder(self, visit):
        ''' nonrecrusive, not mark '''
        stack = []
        node = self.root
        while True:
            if not node:
                while stack and node == stack[-1].rc:
                    node = stack.pop()
                    visit(node)
                if not stack: break
                node = stack[-1].rc
            else:
                stack.append(node)
                node = node.lc

    def inorder(self, visit):
        ''' inorder traverse '''
        stack = []
        node = self.root
        while True:
            if not node:
                if not stack: break
                node  = stack.pop()
                visit(node)
                node = node.rc
            else:
                stack.append(node)
                node = node.lc

def printer(node):
    print(node.v, end=' >')

def main():
    t = Tree('ab##cd###')
    t.preorder(printer)
    t.postorder(printer)
    t.inorder(printer)
if __name__ == '__main__':
    main()
